/**
 * @file   BinaryTree.h
 * @author Wang Heyu <wang@wukong>
 * @date   Fri Nov  1 14:55:58 2019
 * 
 * @brief A teaching demonstration for binary trees. And it will
 * become the basis structure of binary search trees and red-black
 * trees.
 * 
 * 
 */

#ifndef __CRAZYFISH__BINARYTREE__
#define __CRAZYFISH__BINARYTREE__

#define BLACK false
#define RED true

#include <limits>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
/**
 * Minimum number of TYPE type.
 * 
 */
#define MIN (std::numeric_limits<TYPE>::min())

#define RESET "\033[0m"
#define RC "\033[31m" /* Red */
#define WC "\033[37m" /* White */
#define GC "\033[32m" /* Green */
#define YC "\033[33m" /* Yellow */
#define BC "\033[34m" /* Blue */
#define MC "\033[35m" /* Magenta */
#define CC "\033[36m" /* Cyan */

template <class TYPE>
class BinaryTree;

/** 
 * Quite routine for pow function with a base of 2 and integer
 * argument.
 * 
 * @param _x The argument of the function.
 * 
 * @return The pow function value.
 */
inline int __pow2(int _x);

/** 
 * Print out _x consecutive spaces.
 * 
 * @param _x The number of the spaces.
 * 
 * @return 0 for OK.
 */
inline int __make_space(int _x);

/** 
 * Print of a branch for a binary tree node has both two children.
 * 
 * @param _x The length of the branch. 
 * 
 * @return 0 for OK.
 */
inline int __make_both_branch(int _x);
    
/** 
 * Print of a branch for a binary tree node has only left child.
 * 
 * @param _x The length of the branch. 
 * 
 * @return 0 for OK.
 */
inline int __make_left_branch(int _x);

/** 
 * Print of a branch for a binary tree node has only right child.
 * 
 * @param _x The length of the branch. 
 * 
 * @return 0 for OK.
 */
inline int __make_right_branch(int _x);

/**
 * The basic definition of a binary tree.
 * 
 */
template <class TYPE>
class BinaryTree
{
public:
    /**
     * The node structure of the binary tree. Set all members as public
     * for efficiency.
     * 
     */
    class BinaryTreeNode;

    typedef BinaryTreeNode Node;
    
    class BinaryTreeNode
    {
    public:
	TYPE data;		/**< Satellite data, which is
				 * also a key value. */
	BinaryTreeNode *left;	/**< Left child. */
	BinaryTreeNode *right;	/**< Right child. */
	BinaryTreeNode *parent;	/**< Parent.  */
	int depth;		/**< Depth of the node. */
	int pos;		/**< Location in the current
				 * layer in the full binary
				 * tree (including the vacant
				 * node).*/
	bool color = RED;	/**< C++ 11 standard. */

	/** 
	 * Default constructor. 
	 * 
	 */
	BinaryTreeNode(){};

	/** 
	 * Constructor. Copy a node from the given const address.
	 * 
	 * @param _t The const address point to a node(can not be a
	 * NULL).
	 */
	BinaryTreeNode(const BinaryTreeNode *_t)
	{
	    if (_t == NULL)
	    {
		std::cerr << "Error! Can not copy a NULL."
			  << std::endl;
		std::exit(-1);
	    }
	    data = _t->data;
	    parent = left = right = NULL;
	};

	/** 
	 * Constructor. Copy a node from the given address.
	 * 
	 * @param _t The address point to a node(can not be a NULL).
	 */
	BinaryTreeNode(BinaryTreeNode *_t)
	{
	    if (_t == NULL)
	    {
		std::cerr << "Error! Can not copy a NULL."
			  << std::endl;
		std::exit(-1);
	    }
	    data = _t->data;
	    parent = left = right = NULL;
	};

	/** 
	 * Constructor. Create a node with the data is the given
	 * value _d.
	 * 
	 * @param _d Given value.
	 */
	BinaryTreeNode(TYPE _d)
	{
	    data = _d;
	    parent = left = right = NULL;
	};

	/** 
	 * Destructor.
	 * 
	 */
	~BinaryTreeNode(){};
    };
    
protected:
    Node *root;			/**< The address of the root node. And
				 * if the tree is empty, this root
				 * points to the sentinel node nil.*/
    Node *nil;	                /**< The sentinel node, its data,
				 * children and parent are all
				 * insignificance, it is just a mark
				 * for NULL, but has the whole
				 * structure as a normal node. And for
				 * all interfaces, nil will transfer
				 * to NULL.*/
public:
    /** 
     * Default constructor.
     * 
     */
    BinaryTree()
    {
	nil = new Node;
	nil->color = BLACK;
	nil->data = MIN;
	root = nil;
    };

    /** 
     * Constructor. Create a new tree with only one root node, which
     * the the data inside is the given value _new.
     * 
     * @param _new Given value.
     */
    BinaryTree(TYPE _new);

    ~BinaryTree();

    /** 
     * Get the address of the root. This is a read-only version.
     * 
     * 
     * @return The const address of the root.
     */
    const Node *getRoot() const;

    /** 
     * Get the address of the root.
     * 
     * 
     * @return The address of the root.
     */
    Node *getRoot();

    /** 
     * Set the root to the give address, still keep the old root and
     * the sub-tree pointed.
     * 
     * @param _r The new root address.
     * 
     * @return 0 for OK.
     */
    int setRoot(Node *_r);

    /** 
     * Inorder walking and printing the sub-tree root at _x.
     * 
     * @param _x The root of the sub-tree.
     * 
     * @return 0 for OK.
     */
    int inorder_walk(const Node *_x) const;

    /** 
     * Inorder walking and printing the whole tree from the root.
     * 
     * 
     * @return 0 for OK.
     */
    int inorder_walk() const;

    /** 
     * Seach the location of the node contains data _d. If there are
     * more than one nodes, return the first one met. This is a
     * read-only version.
     * 
     * @param _d The data for searching.
     * 
     * @return The address of the node contains _d, and nil if not
     * found.
     */
    const Node *search(TYPE _d) const;

    /** 
     * Seach the location of the node contains data _d. If there are
     * more than one nodes, return the first one met. 
     * 
     * @param _d The data for searching.
     * 
     * @return The address of the node contains _d, and nil if not
     * found.
     */
    Node *search(TYPE _d);

    /** 
     * Find the node whose data is the minimum in the whole tree.
     * 
     * 
     * @return The address of the node with the minimum.
     */
    Node *min();
    
    /** 
     * Find the node whose data is the minimum in the whole tree. This
     * is the read-only version.
     * 
     * 
     * @return The address of the node with the minimum.
     */
    const Node *min() const;

    /** 
     * Find the minimum data in the whole tree.
     * 
     * 
     * @return The minimum.
     */
    TYPE min_value() const;
    
    /** 
     * Find the node whose data is the minimum under the node _x.
     * 
     * 
     * @return The address of the node with the minimum.
     */
    Node *min(Node *_x);
    
    /** 
     * Find the node whose data is the minimum under the node _x. This
     * is the read-only version.
     * 
     * 
     * @return The address of the node with the minimum.
     */
    const Node *min(const Node *_x) const;

    /** 
     * Find the minimum data under the node _x.
     * 
     * 
     * @return The minimum.
     */
    TYPE min_value(const Node *_x) const;

    /** 
     * Find the node whose data is the maximum in the whole tree.
     * 
     * 
     * @return The address of the node with the maximum.
     */
    Node *max();
    
    /** 
     * Find the node whose data is the maximum in the whole tree. This
     * is the read-only version.
     * 
     * 
     * @return The address of the node with the maximum.
     */
    const Node *max() const;

    /** 
     * Find the maximum data in the whole tree.
     * 
     * 
     * @return The maximum.
     */
    TYPE max_value() const;
    
    /** 
     * Find the node whose data is the maximum under the node _x.
     * 
     * 
     * @return The address of the node with the maximum.
     */
    Node *max(Node *_x);
    
    /** 
     * Find the node whose data is the maximum under the node _x. This
     * is the read-only version.
     * 
     * 
     * @return The address of the node with the maximum.
     */
    const Node *max(const Node *_x) const;

    /** 
     * Find the maximum data under the node _x.
     * 
     * 
     * @return The maximum.
     */
    TYPE max_value(const Node *_x) const;

    /** 
     * Delete the whole sub-tree root at _x, and release the memory.
     * 
     * @param _x The root of the sub-tree.
     * 
     * @return 0 for OK.
     */
    int release(Node *_x);

    /** 
     * Delete the whole tree and release the memory.
     * 
     * 
     * @return 0 for OK.
     */
    int release();

    /** 
     * Trans plant the sub-tree root at _u to _v. 
     * 
     * @param _u The root of the source sub-tree.
     * @param _v The root place of the sub-tree trans planting to.
     * 
     * @return 0 for OK.
     */
    int transplant(Node *_u, Node *_v);

    /** 
     * Display the whole binary tree as a full binary tree. The
     * efficiency of this routine is quite low: 
     * \f[
     * T(n) = O(2^n),
     * \f]
     * here \f$ n\f$ is the total nodes of the tree. It just for debugging.
     * 
     * @return 0 for OK.
     */
    int display();

    /** 
     * Comput the height of the sub-tree root at _x. The height of an
     * empty tree is 0, and one node tree is 1.
     * 
     * @param _x The root of the sub-tree.
     * 
     * @return The height value.
     */
    int height(const Node *_x) const;

    /** 
     * Comput the height of the tree.
     * 
     * 
     * @return The height value.
     */
    int height() const;

    /** 
     * Update the depth and position values of all nodes in the
     * tree.
     * 
     * @return 0 for OK.
     */
    int updateDepthandPos();

    /** 
     * Update the depth and position values of all nodes in the
     * sub-tree root at _x.
     * 
     * @param _x The root 0f the sub-tree.
     * @param _d The depth value of _x.
     * @param _p The position value of _x.
     * 
     * @return 0 for OK.
     */
    int updateDepthandPos(Node *_x, int _d, int _p);

    /** 
     * Insert a new node with data _val to the left child of _x,
     * return error if the left child is exist.
     * 
     * @param _x The node to insert under.
     * @param _val The data value for the new node.
     * 
     * @return 0 for OK.
     */
    int insertLeft(Node *_x, TYPE _val);

    /** 
     * Insert a new node with data _val to the right child of _x,
     * return error if the right child is exist.
     * 
     * @param _x The node to insert under.
     * @param _val The data value for the new node.
     * 
     * @return 0 for OK.
     */
    int insertRight(Node *_x, TYPE _val);

    int RightRotate(Node *_x);

    int LeftRotate(Node *_x);

    /** 
     * Find the node with the smallest data greater than the data of
     * _x.
     * 
     * @param _x The start node.
     * 
     * @return The address of the successor node.
     */
    Node *successor(Node *_x);
    
    /** 
     * Find the node with the smallest data greater than the data of
     * _x. This is the read-only version.
     * 
     * @param _x The start node.
     * 
     * @return The address of the successor node.
     */
    const Node *successor(const Node *_x) const;

    /** 
     * Find the smallest data greater than the data of _x.
     * 
     * @param _x The start node.
     * 
     * @return The successor data.
     */
    TYPE succeeding_value(const Node *_x) const;
    
    /** 
     * Find the node with the largest data less than the data of
     * _x.
     * 
     * @param _x The start node.
     * 
     * @return The address of the predecessor node.
     */
    Node *predecessor(Node *_x);

    /** 
     * Find the node with the largest data less than the data of
     * _x. This is the read-only version.
     * 
     * @param _x The start node.
     * 
     * @return The address of the predecessor node.
     */
    const Node *predecessor(const Node *_x) const;
    
    /** 
     * Find the largest data less than the data of _x.
     * 
     * @param _x The start node.
     * 
     * @return The predecessor data.
     */
    TYPE preceding_value(const Node *_x) const;

    /** 
     * Insert a new node to the binary search tree, and keep it as
     * a binary search tree.
     * 
     * @param _new The new node.
     * 
     * @return 0 for OK.
     */
    int insert(Node *_new);
    
    /** 
     * Insert a new node with data _d to the binary search tree, and
     * keep it as a binary search tree.
     * 
     * @param _new The data for the new node.
     * 
     * @return 0 for OK.
     */
    int insert(TYPE _d);

    /** 
     * Delete node _x in the binary search tree, and keep it as a
     * binary search tree.
     * 
     * @param _x The node to delete.
     * 
     * @return 0 for OK.
     */
    int del(Node *_x);
};

template <class TYPE>
typename BinaryTree<TYPE>::Node* BinaryTree<TYPE>::getRoot()
{
    if (root != nil)
	return root;
    else
	return NULL;
};

template <class TYPE>
const typename BinaryTree<TYPE>::Node* BinaryTree<TYPE>::getRoot() const
{
    if (root != nil)
	return (dynamic_cast<const Node *>(root));
    else
	return NULL;
};

template <class TYPE>
BinaryTree<TYPE>::BinaryTree(TYPE _new)
{
    nil = new Node;
    nil->color = BLACK;
    nil->data = MIN;
    Node *r = new Node;
    r->data = _new;
    r->left = nil;
    r->right = nil;
    r->parent = nil;
    root = r;
};

template <class TYPE>
int BinaryTree<TYPE>::inorder_walk(const Node *_x) const
{
    if (_x != nil)
    {
	inorder_walk(_x->left);
	std::cout << _x->data << " ";
	inorder_walk(_x->right);
    }
    return 0;
};

template <class TYPE>
const typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::search(TYPE _d) const
{
    const Node *x = this->root;
    while (x != this->nil && _d != x->data)
	// Here the decision rule has to accord with the one in the
	// insert function.
    	if (_d < x->data)
    	    x = x->left;
    	else
    	    x = x->right;
    return x;
};

template <class TYPE>
typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::search(TYPE _d)
{
    Node *x = this->root;
    while (x != this->nil && _d != x->data)
	// Here the decision rule has to accord with the one in the
	// insert function.
    	if (_d < x->data)
    	    x = x->left;
    	else
    	    x = x->right;
    return x;
};

template <class TYPE>
const typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::min() const
{
    const Node *x = this->root;
    if (x != this->nil)
        while (x->left != this->nil)
            x = x->left;
    return x;
};


template <class TYPE>
typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::min()
{
    Node *x = this->root;
    if (x != this->nil)
	while (x->left != this->nil)
	    x = x->left;
    return x;
};

template <class TYPE>
TYPE BinaryTree<TYPE>::min_value() const
{
    const Node *x = this->root;
    if (x == this->nil)
    {
	std::cerr << "Error! The tree is empty." << std::endl;
	return -1;
    }
    while (x->left != this->nil)
	x = x->left;
    return x->data;
};

template <class TYPE>
typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::max()
{
    Node *x = this->root;
    if (x != this->nil)
	while (x->right != this->nil)
	    x = x->right;
    return x;
};

template <class TYPE>
const typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::max() const
{
    const Node *x = this->root;
    if (x != this->nil)
	while (x->right != this->nil)
	    x = x->right;
    return x;
};

template <class TYPE>
TYPE BinaryTree<TYPE>::max_value() const
{
    const Node *x = this->root;
    if (x == this->nil)
    {
	std::cerr << "Error! The tree is empty." << std::endl;
	return -1;
    }
    while (x->right != this->nil)
	x = x->right;
    return x->data;
};

template <class TYPE>
typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::min(Node *_x)
{
    if (_x != this->nil)
	while (_x->left != this->nil)
	    _x = _x->left;
    return _x;
};

template <class TYPE>
const typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::min(const Node *_x) const
{
    if (_x != this->nil)
	while (_x->left != this->nil)
	    _x = _x->left;
    return _x;
};

template <class TYPE>
TYPE BinaryTree<TYPE>::min_value(const Node *_x) const
{
    if (_x == this->nil)
    {
	std::cerr << "Error! The node is a NULL." << std::endl;
	return -1;
    }
    while (_x->left != this->nil)
	_x = _x->left;
    return _x->data;
};

template <class TYPE>
typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::max(Node *_x)
{
    if (_x != this->nil)
	while (_x->right != this->nil)
	    _x = _x->right;
    return _x;
};

template <class TYPE>
const typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::max(const Node *_x) const
{
    if (_x != this->nil)
	while (_x->right != this->nil)
	    _x = _x->right;
    return _x;
};

template <class TYPE>
TYPE BinaryTree<TYPE>::max_value(const Node *_x) const
{
    if (_x == this->nil)
    {
	std::cerr << "Error! The node is a NULL." << std::endl;
	return -1;
    }
    while (_x->right != this->nil)
	_x = _x->right;
    return _x->data;
};

template <class TYPE>
int BinaryTree<TYPE>::release(Node *_x)
{
    if (_x != nil)
    {
	release(_x->left);
	release(_x->right);
	delete _x;
    }
    return 0;
};

template <class TYPE>
int BinaryTree<TYPE>::release()
{
    release(root);
    delete nil;
    return 0;
};

template <class TYPE>
int BinaryTree<TYPE>::inorder_walk() const
{
    inorder_walk(root);
    std::cout << std::endl;
};

template <class TYPE>
int BinaryTree<TYPE>::setRoot(Node *_r)
{
    root = _r;
    return 0;
};

template <class TYPE>
int BinaryTree<TYPE>::transplant(Node *_u,
			   Node *_v)
{
    if (_u == nil)
    {
	std::cerr << "Error! Can not transplant to a NULL."
		  << std::endl;
	std::exit(-1);
    }
    if (_u->parent == nil)
	root = _v;   /// Here can not use _u = _v;
    else if (_u == _u->parent->left)
	_u->parent->left = _v;
    else
	_u->parent->right = _v;
//    if (_v != nil)
    _v->parent = _u->parent;
    return 0;
};

template <class TYPE>
int BinaryTree<TYPE>::display() 
{
    updateDepthandPos();
    // For breadth-first tree walk. 
    std::queue<Node *> val;
    // For print tree.  
    std::queue<Node *> output;	
    // Children status for a node.
    enum ChildCases {LEFT, RIGHT, BOTH, NONE};
    // The children stauts of nodes outputing. Template
    // queue use local type is a feature from C++ 11.
    std::queue<ChildCases> output_cc;
    // Cache the branches between node and its children. 
    std::queue<ChildCases> branch_cache;
    // Cache the nodes for outputing. 
    std::queue<Node *> node_cache; 
    if (root != nil)
	val.push(root);
    else
    {
	std::cout << "The tree is empty." << std::endl;
	return 0;
    }
    // Height of the whole tree. 
    int h = height();
    // Record the nodes number for each tree layer. 
    std::vector<int> counter(h , 0);
    // Count the number of outputed nodes.  
    int count = 0;		
    // In this loop, we use a queue val to apply a breadth-first tree
    // walking and to record the order of nodes ouputing by another
    // queue output. In the same time, we also record the children
    // status of each outputing node by queue output_cc, and the
    // number of nodes to output in each layer of the tree by vector
    // counter.
    while (!val.empty())
    {
	bool left_exist = false;
	bool right_exist = false;
	Node *next = val.front();
	val.pop();
	if (next->left != nil)
	{
	    val.push(next->left);
	    left_exist = true;
	}
	if (next->right != nil)
	{
	    val.push(next->right);
	    right_exist = true;
	}
	if (left_exist && right_exist)
	    output_cc.push(BOTH);
	else if (left_exist)
	    output_cc.push(LEFT);
	else if (right_exist)
	    output_cc.push(RIGHT);
	else
	    output_cc.push(NONE);
	output.push(next);
	counter[next->depth]++;
    }
    // Because some of the nodes are missing in an imcomplete tree, so
    // we use the variable off to compute the offset of the display
    // positon for every outputing node. That means we actually print
    // out a complete tree! In some cases, such as each node only has
    // right child, the complexity of this function is 2 to the power
    // of n, which is terrible. However, this function obviously is
    // only for small scale debuging usages.
    
    // Offset of the position to display a node. 
    int off = 0;	
    // In this loop, we actually print the tree by using
    // std::cout. With the branches between nodes and their chidren.
    while (!output.empty())
    {
	Node *next = output.front();
	output.pop();
	// Fill the missing nodes.
	while (off < next->pos)
	{
	    __make_space(__pow2(h - next->depth + 1));
	    off++;
	}
	// Offset for centrally print every node.
	__make_space(__pow2(h - next->depth) - 2);
	if (next->color == RED)
	{
	    std::cout << RC;
	    std::cout << std::setw(3) << std::left << next->data;
	    std::cout << RESET;
	}
	else
	{
	    std::cout << WC;
	    std::cout << std::setw(3) << std::left << next->data;
	    std::cout << RESET;
	}
	__make_space(__pow2(h - next->depth) - 1);
	count++;
	off++;
	// Record the printed node, the children status of these to
	// build the branches between nodes and their childern.
	node_cache.push(next);
	branch_cache.push(output_cc.front());
	output_cc.pop();
	// The first condition means all nodes in this layer have been
	// printed, in the next we should print out a enter to start a
	// newline for branches. And the second condition says if we
	// are in the last layer, we don't do it.
	if (count == counter[next->depth] && next->depth != h - 1)
	{
	    count = 0;
	    off = 0;
	    std::cout << std::endl;
	    while (!branch_cache.empty())
	    {
		ChildCases cc = branch_cache.front();
		branch_cache.pop();
		Node *next = node_cache.front();
		node_cache.pop();
		// Again, we need comput the offset for the branches
		// of those missing node.
		while (off < next->pos)
		{
		    __make_space(__pow2(h - next->depth + 1));
		    off++;
		}
		// The offset for centrally print.
		__make_space(__pow2(h - next->depth - 1) - 2);
		// Pick the different type of the branches.
		if (cc == BOTH)
		    __make_both_branch(__pow2(h - next->depth) + 1);
		else if (cc == LEFT)
		    __make_left_branch(__pow2(h - next->depth) + 1);
		else if (cc == RIGHT)
		    __make_right_branch(__pow2(h - next->depth) + 1);
		else if (cc == NONE)
		    __make_space(__pow2(h - next->depth) + 1);
		__make_space(__pow2(h - next->depth - 1) - 2);
		std::cout << "   ";
		off++;
	    }
	    off = 0;
	    std::cout << std::endl;
	}
    }
    std::cout << std::endl;
    return 0;
};

template <class TYPE>
int BinaryTree<TYPE>::updateDepthandPos(Node *_x, int _d, int _p)
{
    if (_x != nil)
    {
	_x->depth = _d;
	_x->pos = _p;
	updateDepthandPos(_x->left, _d + 1, _p * 2);
	updateDepthandPos(_x->right, _d + 1, _p *2 + 1);
    }
    return 0;
};

template <class TYPE>
int BinaryTree<TYPE>::updateDepthandPos()
{
    updateDepthandPos(root, 0, 0);
    return 0;
};

template <class TYPE>
int BinaryTree<TYPE>::height(const Node *_x) const
{
    if (_x == nil)
	return 0;
    else
	return std::max(height(_x->left), height(_x->right)) + 1;
};

template <class TYPE>
int BinaryTree<TYPE>::height() const
{
    return height(root);
};

template <class TYPE>
BinaryTree<TYPE>::~BinaryTree()
{
    release();
};

template <class TYPE>
int BinaryTree<TYPE>::insertLeft(Node *_x, TYPE _val)
{
    if (_x == nil)
    {
	std::cerr << "Error! The tree is empty." << std::endl;
	return -1;
    }
    if (_x->left != nil)
    {
	std::cerr << "Error! The left child is ocuupied." << std::endl;
	return -1;
    }
    Node *t = new Node;
    t->parent = _x;
    t->data = _val;
    t->left = nil;
    t->right = nil;
    _x->left = t;
    return 0;
};

template <class TYPE>
int BinaryTree<TYPE>::insertRight(Node *_x, TYPE _val)
{
    if (_x == nil)
    {
	std::cerr << "Error! The tree is empty." << std::endl;
	return -1;
    }
    if (_x->right != nil)
    {
	std::cerr << "Error! The right child is ocuupied." << std::endl;
	return -1;
    }
    Node *t = new Node;
    t->parent = _x;
    t->data = _val;
    t->left = nil;
    t->right = nil;
    _x->right = t;
    return 0;
};

template <class TYPE>
int BinaryTree<TYPE>::RightRotate(Node *_x)
{
    Node *y = _x->left;
    _x->left = y->right;
    if (y->right != nil)
	y->right->parent = _x;
    y->parent = _x->parent;
    if (_x->parent == nil)
	root = y;
    // if _x is _x's parent's left child,
    else if (_x == _x->parent->left)
	// set y as _x's parent's left child.
	_x->parent->left = y;
    else
	_x->parent->right = y;
    y->right = _x;
    _x->parent = y;
};

template <class TYPE>
int BinaryTree<TYPE>::LeftRotate(Node *_x)
{
    Node *y = _x->right;
    _x->right = y->left;
    if (y->left != nil)
	y->left->parent = _x;
    y->parent = _x->parent;
    if (_x->parent == nil)
	root = y;
    // if _x is _x's parent's left child,
    else if (_x == _x->parent->left)
	// set y as _x's parent's left child.
	_x->parent->left = y;
    else
	_x->parent->right = y;
    y->left = _x;
    _x->parent = y;
};


template <class TYPE> typename BinaryTree<TYPE>::Node *
BinaryTree<TYPE>::successor(Node *_x)
{
    if (_x == this->nil)
    {
	std::cerr << "Error! The node is a NULL." << std::endl;
	return NULL;
    }
    if (_x->right != this->nil)
	return min(_x->right);
    Node *y = _x->parent;
    while (y != this->nil && _x == y->right)
    {
	_x = y;
	y = y->parent;
    }
    return y;
};

template <class TYPE>
const typename BinaryTree<TYPE>::Node *
BinaryTree<TYPE>::successor(const Node *_x) const
{
    if (_x == this->nil)
    {
	std::cerr << "Error! The node is a NULL." << std::endl;
	return NULL;
    }
    if (_x->right != this->nil)
	return min(_x->right);
    // Use const for safty.
    const Node *y = _x->parent;
    while (y != this->nil && _x == y->right)
    {
	_x = y;
	y = y->parent;
    }
    return y;
};

template <class TYPE>
TYPE BinaryTree<TYPE>::succeeding_value(const Node *_x) const
{
    if (_x == this->nil)
    {
	std::cerr << "Error! The node is a NULL." << std::endl;
	std::exit(-1);
    }
    if (_x->right != this->nil)
	return min_value(_x->right);   
    // Use const for safty.
    const Node *y = _x->parent;
    while (y != this->nil && _x == y->right)
    {
	_x = y;
	y = y->parent;
    }
    if (y == this->nil)
    {
	std::cerr << "There is no successor of the maximum node."
		  << std::endl;
	/// return MIN as a signal.
	return MIN;   
    }
    else
	return y->data;
};

template <class TYPE>
typename BinaryTree<TYPE>::Node *
BinaryTree<TYPE>::predecessor(Node *_x)
{
    if (_x == this->nil)
    {
	std::cerr << "Error! The node is a NULL." << std::endl;
	return NULL;
    }

    if (_x->left != this->nil)
	return max(_x->left);
    Node *y = _x->parent;
    while (y != this->nil && _x == y->left)
    {
	_x = y;
	y = y->parent;
    }
    return y;
};

template <class TYPE>
const typename BinaryTree<TYPE>::Node *
BinaryTree<TYPE>::predecessor(const Node *_x) const
{
    if (_x == this->nil)
    {
	std::cerr << "Error! The node is a NULL." << std::endl;
	return NULL;
    }
    if (_x->left != this->nil)
	return max(_x->left);
    const Node *y = _x->parent;
    while (y != this->nil && _x == y->left)
    {
	_x = y;
	y = y->parent;
    }
    return y;
};

template <class TYPE>
TYPE BinaryTree<TYPE>::preceding_value(const Node *_x) const
{
    if (_x == this->nil)
    {
	std::cerr << "Error! The node is a NULL." << std::endl;
	std::exit(-1);
    }
    if (_x->left != this->nil)
	return max_value(_x->left);
    const Node *y = _x->parent;
    while (y != this->nil && _x == y->left)
    {
	_x = y;
	y = y->parent;
    }
    if (y == NULL)
    {
	std::cerr << "There is no predecessor of the minimum node."
		  << std::endl;
	return MIN;
    }
    else
	return y->data;
};

template <class TYPE>
int BinaryTree<TYPE>::insert(Node *_new)
{
    Node *y = this->nil;
    Node *x = this->root;
    // Make sure that _new is a single node binary tree.
    _new->left = _new->right = this->nil;
    while (x != this->nil)
    {
	y = x;
	// The nodes less than to the left, then these greater than or
	// equal to to the right.
	if (_new->data < x->data)
	    x = x->left;
	else
	    x = x->right;
    }
    _new->parent = y;
    if (y == this->nil)
	this->root = _new;
    // Here the decision rule has to same as above.
    else if (_new->data < y->data)
	y->left = _new;
    else
	y->right = _new;
    return 0;
};

template <class TYPE>
int BinaryTree<TYPE>::insert(TYPE _d)
{
    Node *y = this->nil;
    Node *x = this->root;
    Node *z = new Node(_d);
    // Here has to reset the nil, since the Node do not contains the
    // definatio of nil.
    z->left = z->right = this->nil;
    while (x != this->nil)
    {
    	y = x;
	// The nodes less than to the left, then these greater than or
	// equal to to the right.
    	if (z->data < x->data)
    	    x = x->left;
    	else
    	    x = x->right;
    }
    z->parent = y;
    if (y == this->nil)
    	this->root = z;
    // Here the decision rule has to same as above.
    else if (z->data < y->data)
    	y->left = z;
    else
    	y->right = z;
    return 0;
};

template <class TYPE>
int BinaryTree<TYPE>::del(Node *_x)
{
    if (_x->left == this->nil)
	this->transplant(_x, _x->right);
    else if (_x->right == this->nil)
	this->transplant(_x, _x->left);
    else
    {
	// In this branch, _x has two children.  Find the successor of
	// _x, it exists because of the existence of right
	// child. Notice that y don't has left child otherwise it can
	// not be _x's successor(left child of y should less than y
	// and greater than _x).
	Node *y = min(_x->right);
	// If y is not a child of _x, which means y is _x's grand
	// child or lower.
	if (y->parent != _x)   
	{
	    // This actually make a circle. Dangrous! Here we
	    // transplant right child of y to y, but we didn't lose
	    // y. we just make the right child of y become y's
	    // parent's child.
	    this->transplant(y, y->right);
	    // Then make the right child of _x become y's right
	    // child. And still we didn't lose the original right
	    // child of y, it is still y's parent's child.
	    y->right = _x->right;
	    y->right->parent = y;
	    // Suppose z is y's parent in the beginning, till now, y's
	    // right child become z's child, and it's original place
	    // has taken by _x's right child.

	}
	// If y is _x's child, then y is _x's right child because it's
	// a successor of _x. And if not, _x's right child has already
	// transplant to y's right child, while the original right
	// child of y has already transplant to y's parent's
	// child(still in the right subtree of the original _x, now is
	// inside the right subtree of y). In the next we replace _x
	// with y(with the original right subtree of y together with
	// the right subtree of _x), and put the left child of _x to
	// the left child place of y(it's empty before).
	this->transplant(_x, y);
	y->left = _x->left;
	y->left->parent = y;
	// Till now every thing is at the right place excepts _x.
    }
    delete _x;
    return 0;
};                            

inline int __make_space(int _x)
{
    for (int i = 0; i < _x; i++)
	std::cout << " ";
    return 0;
};

inline int __make_both_branch(int _x)
{
    std::cout << "┌";
    for (int i = 0; i < (_x - 3) / 2; i++)
	std::cout << "─";
    std::cout << "┴";
    for (int i = 0; i < (_x - 3) / 2; i++)
	std::cout << "─";
    std::cout << "┐";
    return 0;
};

inline int __make_left_branch(int _x)
{
    std::cout << "┌";
    for (int i = 0; i < (_x - 3) / 2; i++)
	std::cout << "─";
    std::cout << "┘";
    for (int i = 0; i < (_x - 3) / 2; i++)
	std::cout << " ";
    std::cout << " ";
    return 0;
};

inline int __make_right_branch(int _x)
{
    std::cout << " ";
    for (int i = 0; i < (_x - 3) / 2; i++)
	std::cout << " ";
    std::cout << "└";
    for (int i = 0; i < (_x - 3) / 2; i++)
	std::cout << "─";
    std::cout << "┐";
    return 0;
};

inline int __pow2(int _x)
{
    return (1 << _x);
};
#else
// DO NOTHING.
#endif
